I. Field of the Invention
This invention relates to method and apparatus for error correction of stored or transmitted data, and particularly to method and apparatus for decoding codewords to obtain the coefficients of an error/erasure locator polynomial.
II. Prior Art and Other Considerations
Noise occurring in the transmission of data, or in the storing and retrieving of data, can result in errors. Accordingly, various encoding techniques have been developed to specially encode the transmitted or stored data in order to afford an error correction capability.
In accordance with such encoding techniques, a set of message or information bits has a set of check bits appended thereto to form a codeword. The check bits for the codeword are derived by an encoder. In this regard, the encoder essentially treats the bits comprising the set of message bits as coefficients of a binary message polynomial and derives the check bits by operating on the message polynomial (as by multiplication or division) with a generator polynomial G(X). The generator polynomial is selected to impart desired properties to codewords upon which it operates so that the codewords will belong to a particular class of error-correcting binary group codes.
One class of error correcting codes is the well-known BCH codes, which include Reed-Solomon codes. The mathematical basis of Reed-Solomon codes is expounded in Berlekamp, Algebraic Coding Theory, McGraw-Hill, 1968, and summarized in U.S. Pat. No. 4,162,480 to Berlekamp, the latter of which is incorporated herein by reference. According to this exposition, a Reed-Solomon code is one having a generator polynomial G(X) defined as follows: ##EQU1## where .alpha. is a primitive element in the Galois Field GF(2.sup.m), and where d is the code's designed distance. Discussions of Reed-Solomon codes are also provided in other treatises such as Peterson and Weldon, Error-Correcting Codes, Second Edition, The MIT Press, 1972, and Wakerly, Error Detecting Codes, Self-Checking Circuits and Application, North-Holland, 1978.
Upon receipt or retrieval of a transmitted or stored codeword, noise may have added an error pattern to the codeword. To correct for the addition of such an error pattern when dealing with Reed-Solomon codes, a four step procedure is generally utilized. In discussing the error-correcting procedure, we shall consider a Reed-Solomon code consisting of codewords containing n m-bit symbols (of which K symbols are informational symbols and n-K symbols are check symbols). As a first error correcting step, syndrome characters S.sub.o, S.sub.l . . . S.sub.n-K-1 are calculated. As a second step, using the syndrome characters, the coefficients .sigma..sub.o, .sigma..sub.1, .sigma..sub.2, . . . .sigma..sub.n-K-1 of an error locator polynomial .sigma.(X) are calculated. As a third step, the error locator polynomial .sigma.(X) is solved for its roots X.sub.i, which are the error locations in the received codeword. As a fourth step, using the error locations X.sub.i and the syndrome characters S, error values are calculated. Mathematical expressions for the syndrome characters and the coefficients of the error locator polynomial are set forth in the afore-referenced U.S. Pat. No. 4,162,480 to Berlekamp and Chapter 9 of the afore-mentioned Peterson and Weldon treatise.
The second step in the above-described generalized error correcting procedure, i.e., the step of calculating the coefficients of the error locator polynomial, is computationally intensive. A popular algorithm for obtaining the coefficients of the error locator polynomial is the Berlekamp-Massey algorithm. The Berlekamp-Massey algorithm is described in such treaties as the afore-mentioned.
Prior art circuits for solving the Berlekamp-Massey algorithm, and hence for obtaining the coefficients of the error locator polynomial, typically comprise a bank of n-K m-bit shift registers for storing therein a serially input sequence of synromes; a bank of n-K+1 shift registers wherein coefficients of the locator polynomial are accumulated; a plurality of multipliers and an adder connected in a convolution circuit to operate on the values stored in the bank of syndrome shift registers and on the values stored in the bank of coefficient registers to obtain a current discrepancy d.sub.n ; a register for obtaining a prior discrepancy d.sub.m ; a ROM having stored therein a look-up table or the like for performing an inverse operation on the prior discrepancy to obtain a multiplicative inverse d.sub.m.sup.-1 of the prior discrepancy; a multiplier for multiplying the current discrepancy d.sub.n by the inverse d.sub.m.sup.-1 of the prior discrepancy; multipliers for selectively multiplying the product d.sub.n d.sub.m.sup.-1 by the prior contents of registers included in the bank of coefficient registers; and, adders for accumulating the product of the last-mentioned multiplication in the bank of coefficient registers.
Although the prior art circuit described in the preceding paragraph advantageously employs combinatorial finite field multipliers to reduce the number of circuit elements required by earlier vintage circuits, three sets of clock cycles are required in order to perform the three multiplication operations performed thereby. These three multiplication operations are the multiplication effected by the convolution circuit; the multiplication of the current discrepancy by the multiplicative inverse of the prior discrepancy to obtain the product d.sub.n d.sub.m.sup.-1 ; and, the multiplication of the product d.sub.n d.sub.m.sup.-1 by the prior contents of the coefficient registers.
The prior art decoding circuit described above operates on syndromes having what has traditionally been called a "conventional basis" or "alpha basis" representation. In the conventional basis representation of message data, with the message data being a sequence of binary bits, the least significant bit is interpreted as the coefficient of .alpha..sup.0, the next most significant bit as the coefficient of .alpha..sup.1, the next most significant bit as the coefficient of .alpha..sup.2, and so on where .alpha. is an element of a finite field.
As explained in U.S. Pat. No. 4,410,989 to Berlekamp, incorporated herein by reference, a "dual basis" representation, also known as a "beta basis" representation, can also be used to represent message data. The dual basis representation is related to the conventional basis representation by the following set of equations: ##EQU2## where the trace function EQU Tr(X)=x+x.sup.2 +x.sup.2.spsp.2 +. . . +x.sup.2.spsp.m-1
is in the finite Galois Field GF (2.sup.m) of which x is an element.
The afore-referenced U.S. Pat. No. 4,410,989 to Berlekamp discloses a bit serial encoder wherein redundancy bits are realized by a bit serial multiplicative procedure. The Berlekamp '989 patent essentially teaches, for an encoding process, the utilization of representations in dual bases for a multiplier which multiplies by a constant to have a serial output. The Berlekamp '989 patent does not show circuitry for utilizing dual basis representations to obtain the coefficients of an error locator polynomial in a decoding process.
A Reed-Solomon code has minimum distance d.sub.min =n-K+1 and is capable of simultaneously correcting v number of errors and e number of erasures where 2v+e&lt;d.sub.min. An erasure is an error whose location is known but whose magnitude is not.
An erasure locator polynomial .lambda.(X) is definable thusly ##EQU3## where e is the number of erasures (i.e., number of pointers presented) in a codeword. It has been shown by D. O. Carhoun et al (Carhoun, D. O., Johnson, B. L., and Meehan, S. J., "Transform Decoding of Reed-Solomon Codes Volume I: Algorithm and Signal Processing Structure," ESD-TR-82-403, Volume I, November 1982) that, with known .alpha..sup.el, a structure to implement the Berlekamp-Massey Algorithm can also be used to generate the elementary symmetric functions of the erasure locations (.lambda..sub.i), and that by initializing the Berlekamp-Massey Algorithm with these values the algorithm will produce the elementary symmetric functions of error/erasure locations.
In view of the foregoing, it is an object of the present invention to provide method and apparatus for efficiently obtaining the coefficients of an error/erasure locator polynomial in a decoding process.
An advantage of the present invention is the provision of an error/erasure locator circuit usable for efficiently obtaining both the coefficients of an error/erasure locator polynomial and modified syndromes usable for obtaining the magnitudes of errors and erasures.
Another advantage of the present invention is the provision of error/erasure location apparatus and method wherein a cascading multiplier arrangement is utilized to perform three multiplication operations in two rather than three sets of clock cycles in connection with the determination of coefficients of an error/erasure polynomial.
Another advantage of the present invention is the provision of a decoder not requiring a shift register for interfacing a syndrome generator and circuitry used for obtaining the coefficients of an error/erasure locator polynomial.
A further advantage of the present invention is the provision of an error/erasure locator circuit wherein syndrome registers are usable for the dual function of storing both syndrome values and computing modified syndromes usable for obtaining the magnitudes of errors and erasurers.
A yet further advantage of the present invention is the provision of a circuit which uses elementary symmetric functions of the error locations for initialization of the Berlekamp-Massey Algorithm in order to produce the elementary symmetric functions of error/erasure locations.